package com.heima.algorithm.recursion;

/**
 * <h3>递归冒泡排序</h3>
 * <ol>
 *     <li>将数组分为两部分[0……j]，[j+1……arr.length]</li>
 *     <li>左边[0……j]是未排序部分</li>
 *     <li>右边[j+1……arr.length]是已排序部分</li>
 *     <li>未排序区间，相邻两个元素比较，如果前一个大于后一个，则交换位置</li>
 * </ol>
 */

public class BubbleSort {

    /**
     * 对外提供的冒泡排序
     * @param arr 需要进行排序的数组
     */
    public static void bubbleSort(int[] arr) {
        bubbleSort(arr,arr.length - 1);
    }

    /**
     * 将数组一定范围区域内的最大值移到最后
     * @param arr 数组
     * @param boundary 未排序的边界的索引（包含）
     */
    private static void bubbleSort(int[] arr, int boundary) {
        if (boundary == 0){
            return;
        }
        int flag = 0; // 记录发生交换时左边的元素的索引位置，当一轮结束后，flag所在的位置以左是无序的（包含），右边是有序的
        for (int i = 0; i < boundary; i++) {
            if (arr[i] > arr[i + 1]) {
                int temp = arr[i];
                arr[i] = arr[i + 1];
                arr[i + 1] = temp;
                flag = i;
            }
        }
        bubbleSort(arr,flag);
    }
}
